﻿#region

using System;
using System.Collections.Generic;
using System.Linq;
using Domain.Algorithms;

#endregion

namespace Domain {
    public class BlocksFinder {
        private readonly Graph<HyperEdge> graph;
        private List<Graph<HyperEdge>> blocks = new List<Graph<HyperEdge>>();

        public BlocksFinder(Graph<HyperEdge> graph) {
            this.graph = graph;
        }

        private int c;
        private int k;
        private Dictionary<Vertex, int> Dnum;
        private Dictionary<Vertex, int> Low;
        private readonly Stack<Vertex> S = new Stack<Vertex>();

        public List<Graph<HyperEdge>> FindBlocks() {
            Dnum = graph.Vertices.ToDictionary(x => x, x => 0);
            Low = graph.Vertices.ToDictionary(x => x, x => 0);
            c = 0;
            k = 0;
            for (var i = 0; i < graph.NumberVertices; i++) {
                var x = graph.Vertices[i];
                if (Dnum[x] == 0) {
                    Blocks(x);
                }
            }

            FillBlocksWithEdges();

            return blocks;
        }

        private void FillBlocksWithEdges() {
            foreach (var edge in graph.Edges) {
                foreach (var block in blocks) {
                    var vertices = edge.Vertices.Where(vertex => block.Vertices.Contains(vertex)).ToArray();
                    if (vertices.Length > 1) {
                        block.AddEdge(new HyperEdge(vertices));
                    }
                }
            }
        }

        private void Blocks(Vertex x) {
            c++;
            Dnum[x] = c;
            Low[x] = c;
            S.Push(x);
            var neighbourhood = GraphUtils<HyperEdge>.Neighbourhood(graph, x);
            foreach (var y in neighbourhood) {
                if (Dnum[y] == 0) {
                    Blocks(y);
                    Low[x] = Math.Min(Low[x], Low[y]);
                    if (Low[y] == Dnum[x]) {
                        NewBlock(x,y);
                    }
                }
                else {
                    Low[x] = Math.Min(Low[x], Dnum[y]);
                }
            }
        }

        private void NewBlock(Vertex x, Vertex y) {
            k++;
            var vertices = new List<Vertex> {x};
            Vertex z;
            do {
                z = S.Pop();
                vertices.Add(z);
            } while (z != y);
            blocks.Add(new Graph<HyperEdge>(vertices));
        }

       
    }
}